package com.lx.algorithm.code.xly3.class05;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-12 16:16:39
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-12     张李鑫                     1.0         1.0 Version
 */
public class Code02 {
    /**
     * 给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？
     * 比如 s1 = "abcde"，s2 = "axbc"
     * 返回1。s2删掉'x'就是s1的子串了。
     */

    public static int minCost1(String s1, String s2) {
        List<String> list = new ArrayList<String>();
        process(s2, 0, "", list);
        System.out.println(list.size());

        for (String s : list) {
            if (s1.contains(s)) {
                return s1.length() - s.length();
            }
        }
        return s2.length();
    }

    public static int minCost4(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        HashMap<Character, ArrayList<Integer>> map1 = new HashMap<>();
        for (int i = 0; i < str1.length; i++) {
            ArrayList<Integer> list = map1.getOrDefault(str1[i], new ArrayList<Integer>());
            list.add(i);
            map1.put(str1[i], list);
        }
        int ans = 0;
        // 假设删除后的str2必以i位置开头
        // 那么查找i位置在str1上一共有几个，并对str1上的每个位置开始遍历
        // 再次遍历str2一次，看存在对应str1中i后续连续子串可容纳的最长长度
        for (int i = 0; i < str2.length; i++) {
            if (map1.containsKey(str2[i])) {
                ArrayList<Integer> keyList = map1.get(str2[i]);
                for (int j = 0; j < keyList.size(); j++) {
                    int cur1 = keyList.get(j) + 1;
                    int cur2 = i + 1;
                    int count = 1;
                    for (int k = cur2; k < str2.length && cur1 < str1.length; k++) {
                        if (str2[k] == str1[cur1]) {
                            cur1++;
                            count++;
                        }
                    }
                    ans = Math.max(ans, count);
                }
            }
        }
        return s2.length() - ans;
    }


    public static void main(String[] args) {
        int str1Len = 20;
        int str2Len = 10;
        int v = 5;
        int testTime = 10000;
        boolean pass = true;
        System.out.println("test begin");
        for (int i = 0; i < testTime; i++) {
            String str1 = generateRandomString(str1Len, v);
            String str2 = generateRandomString(str2Len, v);
            int ans1 = minCost1(str1, str2);
            int ans4 = minCost4(str1, str2);
            if (ans1 != ans4) {
                pass = false;
                System.out.println(str1);
                System.out.println(str2);
                System.out.println(ans1);
                System.out.println(ans4);
                System.out.println("error");
                break;
            }
        }
        System.out.println("test pass : " + pass);
    }

    public static String generateRandomString(int l, int v) {
        int len = (int) (Math.random() * l);
        char[] str = new char[len];
        for (int i = 0; i < len; i++) {
            str[i] = (char) ('a' + (int) (Math.random() * v));
        }
        return String.valueOf(str);
    }


    private static void process(String s2, int i, String res, List<String> list) {
        if (i == s2.length()) {
            list.add(res);
            return;
        }
        process(s2, i + 1, res + s2.charAt(i), list);
        process(s2, i + 1, res, list);
    }

}
